package dfs;

/**
 * https://leetcode.cn/problems/count-sub-islands/
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493659&idx=1&sn=649bac82e6d6bc488c0dc715ebaac1bb&chksm=9bd41613aca39f057357c8ee3fb9a5e15c10cef72120ec961ffe0238184869def06ff55c7912&scene=178&cur_album_id=2165155308136988673&poc_token=HEzcY2WjeQaXGCgLU4Yx1nRf_rMgUgIuuVL99WZ2
 */
public class _1905_统计子岛屿 {

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid1.length;
        int n = grid1[0].length;

        // 这一题的思路就是把陆地的给淹掉，剩余的就是飞地的大小
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid1[i][j] != grid2[i][j]) {
                    dfs(grid2, i, j);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1) {
                    res += 1;
                    dfs(grid2, i, j);
                }
            }
        }

        return res;
    }


    private void dfs(int[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;

        if (i < 0 || j < 0 || i >= m || j >= n) return;

        if (grid[i][j] == 0) return;

        grid[i][j] = 0;

        //把i，j相邻的岛屿都淹掉
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}
